﻿//////#include <stdio.h>
//////#include <assert.h>
//////#include <stdlib.h>
//////typedef int type;
//////typedef struct BinaryTreeNode
//////{
//////    type date;
//////    struct BinaryTreeNode* left;
//////    struct BinaryTreeNode* right;
//////}BTNode;//相对于给 BinaryTreeNode起个 别名容易记的
//////BTNode* Buynode(type x)
//////{
//////    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//////    if (node == NULL)
//////        return NULL;
//////    node->date = x;
//////    node->left = NULL;
//////    node->right = NULL;
//////}
//////BTNode* Createtree()
//////{
//////    BTNode* node1 = Buynode(1);
//////    BTNode* node2 = Buynode(2);
//////    BTNode* node3 = Buynode(3);
//////    BTNode* node4 = Buynode(4);
//////    BTNode* node5 = Buynode(5);
//////    BTNode* node6 = Buynode(6);
//////    BTNode* node7 = Buynode(7);
//////    node1->left = node2;
//////    node1->right = node4;
//////    node2->left = node3;
//////    node3->left = node7;
//////    node4->left = node5;
//////    node4->right = node6;
//////    return node1;
//////}
//////void preorder(BTNode* root)//前序遍历，根--左子树--右子树
//////{
//////    if (root == NULL)
//////    {
//////        printf("NULL");
//////        return;
//////    }
//////    printf("%d ", root->date);
//////    preorder(root->left);
//////    preorder(root->right);
//////}
//////void inorder(BTNode* root)//中序遍历，左子树--根--右子树
//////{
//////    if (root == NULL)
//////    {
//////        printf("NULL");
//////        return;
//////    }
//////    inorder(root->left);
//////    printf("%d ", root->date);
//////    inorder(root->right);
//////}
//////void postorder(BTNode* root)//后序遍历，左子树--根--右子树
//////{
//////    if (root == NULL)
//////    {
//////        printf("NULL");
//////        return;
//////    }
//////    postorder(root->left);
//////    postorder(root->right);
//////    printf("%d ", root->date);
//////}
////////求结点的个数（第一种方法）
//////int size = 0;
//////void Treesize1(BTNode* root)
//////{
//////    if (root == NULL)
//////        return;
//////    ++size;
//////    Treesize1(root->left);
//////    Treesize1(root->right);
//////}//全局定义size；选择传递地址的方式，不容易错(因为形参的改变不会影响实参，传递地址才可以改变值）
////////求结点的个数（第二种方法）
//////void Treesize2(BTNode* root,int *size)
//////{
//////    if (root == NULL)
//////        return;
//////    ++(*size);
//////    Treesize2(root->left,size);
//////    Treesize2(root->right,size);
//////}
//////int Treesize3(BTNode* root)
//////{
//////    return root==NULL ? 0 : Treesize3(root->left) + Treesize3(root->right) + 1;//+1是因为把本身加进去
//////}
////////求树的高度/深度（树的左子树和右子树大的那个+1（中间的根）
//////int Treeheight(BTNode* root)//
//////{
//////    if (root == NULL)
//////        return 0;
//////    else
//////    {
//////        int leftheight = Treeheight(root->left);//先把数据存起来
//////        int rightheight = Treeheight(root->right);
//////        return leftheight >rightheight? leftheight + 1 :rightheight + 1;
//////    }
//////}
////////求第k层结点的个数
//////int Treeklevel(BTNode* root,int k)
//////{
//////    if (root == NULL)
//////        return 0;
//////    if (k == 1)
//////        return 1;
//////    int leftk = Treeklevel(root->left, k - 1);
//////    int rightk = Treeklevel(root->right, k - 1);
//////    return leftk + rightk;
//////    //return Treeklevel(root->left, k - 1)+ Treeklevel(root->right, k - 1);
//////}
//////int main()
//////{
//////    BTNode* root = Createtree();
//////    preorder(root); printf("\n");
//////    inorder(root); printf("\n");
//////   postorder(root);printf("\n");
//////    Treesize1(root);
//////    printf("size1:%d\n", size);
//////    int size2 = 0;
//////    Treesize2(root,&size2);
//////    printf("size2:%d\n", size2);
//////    printf("size3:%d\n", Treesize3(root));
//////    printf("height:%d\n", Treeheight(root)); 
//////    printf("klevel:%d\n", Treeklevel(root,2));
//////    return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char *str,int *i)传参安全，利用已经知道的先序遍历求先序遍历，中序，后序遍历结果
//////{
//////	if (str[*i] == '#')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str,i);
//////		node->right= createtree(str,i);
//////		return node;
//////	}
//////}
//////void preorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	printf("%c", root->date);
//////	preorder(root->left);
//////	preorder(root->right);
//////}
//////void inorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	inorder(root->left);
//////	printf("%c", root->date);
//////	inorder(root->right);
//////}
//////void postorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	postorder(root->left);
//////	postorder(root->right);
//////	printf("%c", root->date);
//////}
//////int main()
//////{
//////	int t;
//////	scanf("%d", &t);
//////	getchar();//空格
//////	for (int k = 0; k < t; k++)
//////	{
//////		int i = 0;
//////		char* str = (char*)malloc(100*sizeof(char));//多给缓冲区
//////		scanf("%s", str,100);
//////		BTnode* root = createtree(str,&i);
//////		preorder(root);
//////		printf("\n");
//////		inorder(root);
//////		printf("\n");
//////		postorder(root);
//////		printf("\n");
//////		free(str);
//////	}	
//////	return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char* str, int* i)
//////{
//////	if (str[*i] == '0')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str, i);
//////		node->right = createtree(str, i);
//////		return node;
//////	}
//////}
//////void preorder(BTnode* root,int *i)
//////{
//////	if (root == NULL)
//////		return;
//////	else if (root->left == NULL && root->right == NULL)
//////	{
//////		(*i)++;
//////	}
//////		preorder(root->left, i);都需要遍历
//////		preorder(root->right, i);
//////}
//////int main()
//////{
//////	int t;
//////	scanf("%d", &t);
//////	getchar();
//////	for (int k = 0; k < t; k++)
//////	{
//////		int i = 0;
//////		char* str = (char*)malloc(100 * sizeof(char));
//////		scanf("%s", str, 100);
//////		BTnode* root = createtree(str, &i);
//////		int count = 0;
//////		preorder(root,&count);//传地址的话可以改变形参，所以函数不需要返回值
//////		printf("%d\n",count);
//////		free(str);
//////	}
//////	return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char* str, int* i)
//////{
//////	if (str[*i] == '0')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str, i);
//////		node->right = createtree(str, i);
//////		return node;
//////	}
//////}
//////void preorder(BTnode* root, int* i)
//////{
//////	if (root == NULL)
//////		return;
//////	else if (root->left != NULL)
//////	{
//////		if (root->left->left == NULL && root->left->right== NULL)
//////		{
//////			(*i)++;
//////		}
//////	}
//////	preorder(root->left, i);
//////	preorder(root->right, i);
//////}
//////int main()
//////{
//////	int t;
//////	scanf_s("%d", &t);
//////	getchar();
//////	for (int k = 0; k < t; k++)
//////	{
//////		int i = 0;
//////		char* str = (char*)malloc(100 * sizeof(char));
//////		scanf_s("%s", str, 100);
//////		BTnode* root = createtree(str, &i);
//////		int count = 0;
//////		preorder(root, &count);
//////		printf("%d\n", count);
//////		free(str);
//////	}
//////	return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char* str, int* i)
//////{
//////	if (str[*i] == '0' || str[*i] == '\0')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str, i);先序遍历，先根--
//////		node->right = createtree(str, i);
//////		return node;
//////	}
//////}
//////void pleaves(BTnode* root, int* i)
//////{
//////	if (root == NULL)
//////		return;
//////	if (root->left != NULL)
//////	{
//////		if (root->left->left == NULL && root->left->right == NULL)
//////		{
//////			printf("%c ", root->left->date);
//////			(*i)++;
//////		}
//////	}
//////	pleaves(root->left, i);
//////	if (root->right != NULL)
//////	{
//////		if (root->right->left == NULL && root->right->right == NULL)
//////		{
//////			printf("%c ", root->right->date);
//////			(*i)++;
//////		}
//////	}
//////	pleaves(root->right, i);
//////}
//////void parent(BTnode* root, int* i)
//////{
//////	if (root == NULL)
//////		return;
//////	if (root->left != NULL)
//////	{
//////		if (root->left->left == NULL && root->left->right == NULL)
//////		{
//////			printf("%c ", root->date);
//////			(*i)++;
//////		}
//////	}
//////	parent(root->left, i);
//////	if (root->right != NULL)
//////	{
//////		if (root->right->left == NULL && root->right->right == NULL)
//////		{
//////			printf("%c ", root->date);
//////			(*i)++;
//////		}
//////	}
//////	parent(root->right, i);
//////}
//////void freeTree(BTnode* root)
//////{
//////	if (root == NULL) return;
//////	freeTree(root->left);   
//////	freeTree(root->right);  
//////	free(root);             
//////}
//////int main()
//////{
//////	int t;
//////	scanf_s("%d", &t);
//////	getchar();//字符才要，int类型不需要
//////	for (int k = 0; k < t; k++)
//////	{
//////		int i = 0;
//////		char* str = (char*)malloc(100 * sizeof(char));
//////		scanf_s("%s", str, 100);
//////		BTnode* root = createtree(str, &i);
//////		if (root != NULL && root->left == NULL && root->right == NULL)
//////		{
//////			printf("%c ", root->date);
//////			printf("%c\n", root->date);
//////		}
//////		else
//////		{
//////			int count = 0;
//////			pleaves(root, &count);
//////			int num = 0;
//////			printf("\n");
//////			parent(root, &num);
//////			printf("\n");
//////		}
//////		freeTree(root);
//////		free(str);
//////	}
//////	return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	int date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(int x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(int* arr, int i,int len)
//////{
//////	if (arr[i-1] == 0||i>len)
//////	{
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(arr[i-1]);
//////		node->left = createtree(arr, 2*i,len);
//////		node->right = createtree(arr, 2*i+1,len);
//////		return node;
//////	}
//////}
//////void preorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	printf("%d ", root->date);
//////	preorder(root->left);
//////	preorder(root->right);
//////}
//////void freeTree(BTnode* root)
//////{
//////	if (root == NULL) return;
//////	freeTree(root->left);
//////	freeTree(root->right);
//////	free(root);
//////}
//////int main()
//////{
//////	int t,len;
//////	scanf_s("%d", &t);
//////	for (int k = 0; k < t; k++)
//////	{
//////		scanf_s("%d", &len);
//////		int* arr = (int*)malloc(len*sizeof(int));
//////		for (int j = 0; j < len; j++)
//////		{
//////			scanf_s("%d", &arr[j]);
//////		}
//////		BTnode* root = createtree(arr,1,len);
//////		preorder(root);
//////		printf("\n");
//////		freeTree(root);
//////		free(arr);
//////	}
//////	return 0;
//////#include <stdio.h>
//////#include <stdlib.h>
//////#include <string.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////typedef struct
//////{
//////	int top;
//////	int size;
//////	BTnode** date;
//////}S1qstack;
//////typedef struct
//////{
//////	int top;
//////	int size;
//////	int* date;
//////}S2qstack;
//////void inits1(S1qstack* s, int len)
//////{
//////	s->size = len;
//////	s->top = -1;
//////	s->date = (BTnode**)malloc(len*sizeof(BTnode*));
//////}
//////void inits2(S2qstack* s, int len)
//////{
//////	s->size = len;
//////	s->top = -1;
//////	s->date = (int*)malloc(len * sizeof(int));
//////}
//////int Pushs1(S1qstack* s,BTnode* t)
//////{
//////	if (s->top == s->size - 1)
//////	{
//////		return -1;
//////	}
//////	else
//////	{
//////		s->top++;
//////		s->date[s->top] = t;
//////		return 1;
//////	}
//////}
//////int Pushs2(S2qstack* s, int tag)
//////{
//////	if (s->top == s->size - 1)
//////	{
//////		return -1;
//////	}
//////	else
//////	{
//////		s->top++;
//////		s->date[s->top] = tag;
//////		return 1;
//////	}
//////}
//////BTnode* Pops1(S1qstack* s)
//////{
//////	if (s->top == -1)
//////	{
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* p= s->date[s->top];
//////		s->top--;
//////		return p;
//////	}
//////}
//////int Pops2(S2qstack* s)
//////{
//////	if (s->top == -1)
//////	{
//////		return -1;
//////	}
//////	else
//////	{
//////		int tag = s->date[s->top];
//////		s->top--;
//////		return tag;
//////	}
//////}
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char* str, int* i )
//////{
//////	if (str[*i] == '0')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str, i);
//////		node->right = createtree(str, i);
//////		return node;
//////	}
//////}
//////void freeTree(BTnode* root)
//////{
//////	if (root == NULL) return;
//////	freeTree(root->left);
//////	freeTree(root->right);
//////	free(root);
//////}
//////int main()
//////{
//////	int t, len;
//////	scanf_s("%d", &t);
//////	getchar();
//////	for (int j = 0; j < t; j++)
//////	{
//////		int i = 0;
//////		int len = 0;
//////		char* str = (char*)malloc(1000 * sizeof(char));
//////		scanf_s("%s", str,1000);
//////		len = strlen(str);
//////		BTnode* root = createtree(str, &i);
//////		S1qstack S1;
//////		S2qstack S2;
//////		inits1(&S1, len);
//////		inits2(&S2, len);
//////		if (root == NULL)
//////		{
//////			return 0;
//////		}
//////		BTnode* p = root;
//////		do
//////		{
//////			if (p)
//////			{
//////
//////				{
//////					Pushs1(&S1, p);
//////					Pushs2(&S2, 0);
//////					p = p->left;
//////				}
//////			}
//////			else
//////			{
//////				if (S1.top == -1)
//////					break;
//////				int tag = S2.date[S2.top];
//////				if (tag == 0)
//////				{
//////					S2.date[S2.top] = 1;
//////					p = S1.date[S1.top]->right;
//////				}
//////				else
//////				{
//////					BTnode* node = Pops1(&S1);
//////					Pops2(&S2);
//////					printf("%c", node->date);
//////					p = NULL;
//////				}
//////			}
//////		}while (S1.top!=-1);
//////		printf("\n");
//////		freeTree(root);
//////		free(str);
//////	}
//////	return 0;
//////}
//////#include <stdio.h>
//////#include <stdlib.h>
//////#define CRT_SECURE_NO_WARNINGS
//////typedef struct BTnode
//////{
//////	char date;
//////	struct BTnode* left;
//////	struct BTnode* right;
//////}BTnode;
//////BTnode* buytree(char x)
//////{
//////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
//////	node->date = x;
//////	node->left = NULL;
//////	node->right = NULL;
//////	return node;
//////}
//////BTnode* createtree(char *str,int *i)
//////{
//////	if (str[*i] == '#')
//////	{
//////		(*i)++;
//////		return NULL;
//////	}
//////	else
//////	{
//////		BTnode* node = buytree(str[*i]);
//////		(*i)++;
//////		node->left = createtree(str,i);
//////		node->right= createtree(str,i);
//////		return node;
//////	}
//////}
//////void preorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	printf("%c ", root->date);
//////	preorder(root->left);
//////	preorder(root->right);
//////}
//////void inorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	inorder(root->left);
//////	printf("%c ", root->date);
//////	inorder(root->right);
//////}
//////void postorder(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	postorder(root->left);
//////	postorder(root->right);
//////	printf("%c ", root->date);
//////}
//////void cxorder(BTnode* root)
//////{
//////	if (root == NULL)
//////	{
//////		return;
//////	}
//////	BTnode* queue[1000];
//////	int front = 0;
//////	int rear = 0;
//////	queue[rear++] = root;
//////	while (front < rear)
//////	{
//////		BTnode* node = queue[front++];
//////		printf("%c ", node->date);
//////		if (node->left != NULL)
//////		{
//////			queue[rear++] = node->left;
//////		}
//////		if (node->right != NULL)
//////		{
//////			queue[rear++] = node->right;
//////		}
//////	}
//////}
//////void mirror(BTnode* root)
//////{
//////	if (root == NULL)
//////		return;
//////	BTnode* temp=root->right;
//////	root->right = root->left;
//////	root->left = temp;
//////	mirror(root->left);
//////	mirror(root->right);
//////}
//////int main()
//////{
//////	int t;
//////	scanf_s("%d", &t);
//////	getchar();
//////	for (int k = 0; k < t; k++)
//////	{
//////		int i = 0;
//////		char str[1000];
//////		scanf_s("%s", str,1000);
//////		BTnode* root = createtree(str,&i);
//////		if (root == NULL)
//////		{
//////			printf("NULL\nNULL\nNULL\nNULL\n");
//////			continue;
//////		}
//////			mirror(root);
//////			preorder(root);
//////			printf("\n");
//////			inorder(root);
//////			printf("\n");
//////			postorder(root);
//////			printf("\n");
//////			cxorder(root);
//////			printf("\n");
//////		
//////	}	
//////	return 0;
//////}
////#include <stdio.h>
////#include <stdlib.h>
////#define CRT_SECURE_NO_WARNINGS
////typedef struct BTnode
////{
////	char date;
////	struct BTnode* left;
////	struct BTnode* right;
////}BTnode;
////BTnode* buytree(char x)
////{
////	BTnode* node = (BTnode*)malloc(sizeof(BTnode));
////	node->date = x;
////	node->left = NULL;
////	node->right = NULL;
////	return node;
////}
////BTnode* createtree(char* str, int* i)
////{
////		BTnode* node = buytree(str[*i]);
////		(*i)++;
////		node->left = createtree(str, i);
////		(*i)++;
////		node->right = createtree(str, i);
////		return node;
////	}
////}
////void preorder(BTnode* root)
////{
////	if (root == NULL)
////		return;
////	printf("%c ", root->date);
////	preorder(root->left);
////	preorder(root->right);
////}
////void inorder(BTnode* root)
////{
////	if (root == NULL)
////		return;
////	inorder(root->left);
////	printf("%c ", root->date);
////	inorder(root->right);
////}
////void postorder(BTnode* root)
////{
////	if (root == NULL)
////		return;
////	postorder(root->left);
////	postorder(root->right);
////	printf("%c ", root->date);
////}
////void cxorder(BTnode* root)
////{
////	if (root == NULL)
////	{
////		return;
////	}
////	BTnode* queue[1000];
////	int front = 0;
////	int rear = 0;
////	queue[rear++] = root;
////	while (front < rear)
////	{
////		BTnode* node = queue[front++];
////		printf("%c ", node->date);
////		if (node->left != NULL)
////		{
////			queue[rear++] = node->left;
////		}
////		if (node->right != NULL)
////		{
////			queue[rear++] = node->right;
////		}
////	}
////}
//// }
/////*void levelorder(BTnode* root)
////{
////	if (root == NULL)
////	{
////		return;
////	}
////	queue<BTnode*> q;
////	q.push(root);
////	while (!q.empty())
////	{
////		BTnode* node = q.front();
////		q.pop();
////		printf("%d ", node->date);
////		if (node->left)
////			q.push(node->left);
////		if (node->right)
////			q.push(node->right);
////	}
////}*/
////void mirror(BTnode* root)
////{
////	if (root == NULL)
////		return;
////	BTnode* temp = root->right;
////	root->right = root->left;
////	root->left = temp;
////	mirror(root->left);
////	mirror(root->right);
////}
////int main()
////{
////	int n,m;
////	scanf_s("%d", &n);
////	scanf_s("%d", &m);
////	getchar();
////	for (int k = 0; k < n; k++)
////	{
////		int i = 0;
////		char* str=(char*)malloc(n*sizeof(char));
////		scanf_s("%s", str, 1000);
////		BTnode* root = createtree(str, &i);
////	}
////		
////		preorder(root);
////		printf("\n");
////		inorder(root);
////		printf("\n");
////		postorder(root);
////		printf("\n");
////		cxorder(root);
////		printf("\n");
////
////	}
////	return 0;
////}
////#include <iostream>
////#include <stack>
////using namespace std;
////typedef struct BTnode
////{
////	char data;
////	struct BTnode* left;
////	struct BTnode* right;
////};
////非递归先序遍历
////void fun(BTnode* root)
////{
////	BTnode* p = root;
////	stack<BTnode*>s;
////	while (!(p == NULL && s.empty()))
////	{
////		if (p == NULL && s.empty())
////				break;直接放到循环条件里面
////		if (p != NULL)
////		{
////			s.push(p);
////			cout << p->data << " ";//这句位置与中序不一样
////			p = p->left;
////		}
////		else
////		{
////			p = s.top();
////			s.pop();
////			p = p->right;
////		}
////	}
////}
////非递归中序遍历
////void fun(BTnode* root)
////{
////	BTnode* p = root;
////	stack<BTnode*>s;
////	while (!(p == NULL && s.empty()))
////	{
////		if (p == NULL && s.empty())
////				break;直接放到循环条件里面
////		if (p != NULL)
////		{
////			s.push(p);
////			p = p->left;
////		}
////		else
////		{
////			p = s.top();
////			cout << p->data << " ";//位置与先序遍历不一样
////			s.pop();
////			p = p->right;
////		}
////	}
////}
////#include <iostream>
////#include <queue>
////#include <string>
////using namespace std;
////typedef struct BTnode
////{
////	char data;
////	struct BTnode* leftchild;
////	struct BTnode* rightchild;
////	struct BTnode* parent;
////}BTnode;
////BTnode* buytree(char x)
////{
////	if (x == '-')
////		return NULL;
////	BTnode* node = new BTnode();
////	node->data = x;
////	node->leftchild = NULL;
////	node->rightchild = NULL;
////	node->parent = NULL;
////	return node;
////}
////BTnode* levelorder(BTnode* root, char ch)
////{
////	if (root == NULL||ch=='-')
////		return NULL;
////	queue<BTnode*> q;
////	q.push(root);
////	while (!q.empty())
////	{
////		BTnode* node = q.front();
////
////		q.pop();
////		if (node->data == ch)
////		{
////			return node;
////		}
////		if (node->leftchild)
////			q.push(node ->leftchild);
////		if (node->rightchild)
////			q.push(node ->rightchild);
////
////	}
////	return NULL;
////}
////void createtree(BTnode** root, string str)
////{
////	BTnode* node[3] = { NULL };
////	BTnode* temp;
////	for (int i = 0; i < 3; i++)
////	{
////		if (str[i] == '-')
////		{
////			node[i] = NULL;
////			continue;
////		}
////		temp = levelorder(*root, str[i]);
////		if (i == 0 && *root == NULL)
////		{
////			*root = buytree(str[i]);
////			node[i] = *root;
////		}
////		else if (temp != NULL)
////		{
////			node[i] = temp;
////			if (temp == *root)
////			{
////				*root = node[0];
////			}
////		}
////		else
////		{
////			node[i] = buytree(str[i]);
////		}
////	}
////	if (node[0] != NULL&&node[1]!=NULL)
////	{
////		node[0]->leftchild = node[1];
////		node[1]->parent = node[0];
////	}
////	if (node[0] != NULL && node[2] != NULL)
////	{
////		node[0]->rightchild = node[2];
////		node[2]->parent = node[0];
////	}
////}
////void check(BTnode* root, char x, char y)
////{
////	BTnode* node1 = levelorder(root, x);
////	BTnode* node2 = levelorder(root, y);
////	if (node1 == NULL || node2 == NULL)
////	{
////		cout << "-" << endl;
////		return;
////	}
////	else
////	{
////		int flag = 0;
////		int count = 0;
////		BTnode* node1_ = node1;
////		BTnode* node2_ = node2;
////		while (node1_->parent != NULL)
////		{
////			node1_ = node1_->parent;
////			count++;
////			if (node1_ == node2)
////			{
////				flag = 1;
////				break;
////			}
////		}
////		if (flag == 0)
////		{
////			count = 0;
////			while (node2_->parent != NULL)
////			{
////				node2_ = node2_->parent;
////				count++;
////				if (node2_ == node1)
////				{
////					flag = -1;
////					break;
////				}
////			}
////		}
////		if (flag != 0)
////		{
////			if (count == 2)
////				cout << "grand";
////			else if (count > 2)
////			{
////				for (int k = 0; k < count - 2; k++)
////				{
////					cout << "great-";
////				}
////				cout << "grand";
////			}
////			if (flag == 1)
////				cout << "parent" << endl;
////			else if(flag==-1)
////				cout << "child" << endl;
////		}
////		else
////			cout << "-" <<endl;
////	}
////}
////void freetree(BTnode* root)
////{
////	if (root == NULL)
////		return;
////	freetree(root->leftchild);
////	freetree(root->rightchild);
////	delete root;
////}
////int main()
////{
////	int n, m;
////	string str;
////	char x, y;
////	while (cin >> n >> m)
////	{
////		cin.ignore();
////		if (n == 0 && m == 0)
////		{
////			break;
////		}
////		BTnode* root = NULL;
////		for (int k = 0; k < n; k++)
////		{
////			getline(cin, str);
////			createtree(&root, str);
////		}
////		for (int j = 0; j < m; j++)
////		{
////			cin >> x >> y;
////			check(root, x, y);
////		}
////		freetree(root);
////		root= NULL;
////	}
////	return 0;
////}
//#include <iostream>
//#include <string>
//#include <queue>
//using namespace std;
//typedef struct BTnode
//{
//	char data;
//	BTnode* left;
//	BTnode* right;
//}BTnode;
//BTnode* buytree(char x)
//{
//	BTnode* node=new BTnode;
//	node->data = x;
//	node->left = NULL;
//	node->right = NULL;
//	return node;
//}
//BTnode* precreatetree(string str, int* i)
//{
//	BTnode* node;
//	if (*i >= str.size())
//	{
//		(*i)++;
//		return NULL;
//	}
//	if (str[*i] == '#')
//	{
//		node = buytree(str[*i]);
//		(*i)++;
//		node->data = '#';//先序遍历这里NULL使用‘#’代替
//		node->left = NULL;
//		node->right = NULL;
//	}
//	else
//	{
//		node = buytree(str[*i]);
//		(*i)++;
//		node->left = precreatetree(str, i);
//		node->right = precreatetree(str, i);
//	}
//	return node;
//}
//void levelcreatetree(BTnode* root,string str)
//{
//	int i = 0;
//	queue<BTnode*> q;
//	q.push(root);
//	BTnode* p;
//	while (i <str.length())
//	{
//		p = q.front();
//		q.pop();
//		if (p) {
//			if (p->data != str[i])
//			{
//				cout << "NO" << endl;//发现有不想符合的就直接NO
//				return;
//			}
//			q.push(p->left);
//			q.push(p->right);
//		}
//		i++;
//	}
//	cout << "YES" << endl;
//}
//void freetree(BTnode* root)
//{
//	if (root == NULL)
//		return;
//	freetree(root->left);
//	freetree(root->right);
//	delete root;
//}
//int main()
//{
//	int t;
//	cin >> t;
//	cin.ignore();
//	string str, prestr;
//	for (int k = 0; k < t; k++)
//	{
//		int i = 0;
//		getline(cin, str);
//		getline(cin, prestr);
//		BTnode* root =precreatetree(prestr,&i);
//		levelcreatetree(root,str);
//		freetree(root);
//	}
//	return 0;
//}
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef struct BTnode
{
	char data;
	struct BTnode* left;
	struct BTnode* right;
}BTnode;
typedef struct BTnoderesult
{
	int height;
	BTnode* node;
}BTnoderesult;
BTnode* buytree(char x)
{
	BTnode* node = new BTnode;
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}
BTnode* createtree(string str, int* i)
{
	if (*i >= str.size() || str[*i] == '#')
	{
		(*i)++;
		return NULL;
	}
	else
	{
		BTnode* node = buytree(str[*i]);
		(*i)++;
		node->left = createtree(str, i);
		node->right = createtree(str, i);
		return node;
	}
}
BTnode* minNode(BTnode* a, BTnode* b) {
	if (a == NULL) 
		return b;
	if (b == NULL)
		return a;
	return (a->data < b->data) ? a : b;
}
BTnoderesult heightordrt(BTnode* root,int& maxh,BTnode*& node1,BTnode*& node2)
{
	BTnoderesult result;
	if (root == NULL)
	{
		result.height = 0;
		result.node = NULL;
		return result;
	}
	else
	{
		BTnoderesult lefth= heightordrt(root->left,maxh,node1,node2);
		BTnoderesult righth = heightordrt(root->right,maxh,node1,node2);
		result.height = (lefth.height > righth.height) ? lefth.height + 1 : righth.height + 1;
		if (lefth.height > righth.height)
		{
			if (lefth.node != NULL)
				result.node = lefth.node;
			else
				result.node = root;
		}
		else if (lefth.height < righth.height)
		{
			if (righth.node != NULL)
				result.node = righth.node;
			else
				result.node = root;
		}
		else
		{
			result.node = minNode(lefth.node, righth.node);
			if (result.node == NULL)
			{
				result.node = root;
			}
		}
		int maxheight = lefth.height + righth.height;
		BTnode* current1;
		BTnode* current2;
		if (lefth.node != NULL)
			current1 = lefth.node;
		else
			current1 = root;
		if (righth.node != NULL)
			current2 = righth.node;
		else
			current2 = root;
		if (current1->data > current2->data)
		{
			swap(current1, current2);
		}
		if (maxheight > maxh)
		{
			maxh = maxheight;
			node1 = current1;
			node2 = current2;
		}
		else if(maxheight==maxh && maxh > 0)
		{
			if (node1->data > node2->data)
			{
				swap(node1, node2);
			}
			if (current1->data < node1->data)
			{
				node1 = current1;
				node2 = current2;
			}
			else if (current1->data == node1->data)
			{
				if (current2->data < node2->data)
				{
					node1 = current1;
					node2 = current2;
				}
			}
		}
	}
	return result;
}
int compare(BTnode* root,BTnode* &node1,BTnode* &node2)
{
	int maxh = 0;
	node1 = NULL;
	node2 = NULL;
	if (root != NULL)
	{
		heightordrt(root, maxh, node1, node2);
		if (maxh == 0)
		{
			node1 = node2 = root;
		}
	}
	return maxh;
}
void freetree(BTnode* root) {
	if (root == NULL) return;
	freetree(root->left);
	freetree(root->right);
	delete root;
}
int main()
{
	int t;
	cin >> t;
	cin.ignore();
	string str;
	for (int i = 0; i <  t; i++)
	{
		int j = 0;
		getline(cin, str);
		BTnode* root = createtree(str, &j);
		BTnode* node1 = NULL;
		BTnode* node2 = NULL;
		int max = compare(root, node1, node2);;
		cout << max<<":";
		if (max>0&&node1!=NULL && node2 !=NULL)
		{
			cout << node1->data << " " << node2->data;
		}
		cout << endl;
		freetree(root);
	}
	return 0;
}